package com.lfg.leetcode.leetcode100;

import com.lfg.leetcode.leetcode0.TreeNode;

import java.util.*;


public class No107levelOrderBottom {
    public static void main(String[] args) {
        List ret = levelOrderBottom(TreeNode.stringToTreeNode("[3,9,20,null,null,15,7]"));
        System.out.println("[" + ret + "]");
    }

    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret =new LinkedList<>();
        if(root == null){
            return  ret;
        }
        Queue<TreeNode> list = new LinkedList<>();
        list.add(root);

        while(!list.isEmpty()){
            int size = list.size();
            List<Integer> data = new ArrayList<>(size);
            for(int i = 0; i< size; i++){
                TreeNode node = list.poll();
                data.add(node.val);
                if(node.left != null){
                    list.offer(node.left);
                }
                if(node.right != null){
                    list.offer(node.right);
                }
            }
            ret.add(0, data);
        }

        return ret;
    }
}
